#!/usr/bin/env python

#    Copyright 2011,2012 Erik Persson
#
#    This file is part of the cell-sync-usrp project.
#
#    cell-sync-usrp is free software: you can redistribute it and/or modify
#    it under the terms of the GNU General Public License as published by
#    the Free Software Foundation, either version 3 of the License, or
#    (at your option) any later version.
#
#    cell-sync-usrp is distributed in the hope that it will be useful,
#    but WITHOUT ANY WARRANTY; without even the implied warranty of
#    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
#    GNU General Public License for more details.
#
#    You should have received a copy of the GNU General Public License
#    along with cell-sync-usrp.  If not, see <http://www.gnu.org/licenses/>.



""" Class defining a binary array """
class BinaryArray:
    _value = [0]
    _maxlen = 0
    
    def __init__(self,maxlen = 0):
        self._maxlen = maxlen
        i = 0
        self._value = []
        while(i<maxlen):
            self._value.append(0)
            i+=1
        return;
    
    def __str__(self):
        return str(self._value)
    
    def __repr__(self):
        return self.__str__()
        
    def clone(self):
        clone = BinaryArray(self._maxlen)
        clone._value = list(self._value)
        return clone
        
    
    def add(self,boolean):
        if (boolean > 1):
            boolean = 1
            

        if (len(self._value)==0):
            self._value = [boolean]
        else:
            reminder = boolean
            newarray = []

            i = 0
            while (i<len(self._value)):
                v = self._value[i]+reminder
                
                reminder = 0            
                if (v > 1):
                    reminder=1
                    v=0
                
                self._value[i] = v
                i+=1
                
            if ((self._maxlen == 0) or (len(self._value) < self._maxlen)):
                if (reminder > 0):
                    self._value.append(1)
                
#            for a in self._value:
#                v = a+reminder
#                
#                reminder = 0            
#                if (v > 1):
#                    reminder=1
#                    v=0
#                
#                newarray.append(v)
#            
#            if (reminder > 0):
#                newarray.append(1)
#            self._value = newarray


""" Class defining a state """
class State:
    _state = []
    def __init__(self, obj):
        self._state = obj
        
    def __str__(self):
        return str(self._state)
    
    def __repr__(self):
        return self.__str__()
    
    

""" Class defining a output state """
class OutputState:
    _state = []
    def __init__(self, obj):
        self._state = obj
        
    def __str__(self):
        return str(self._state)
    
    def __repr__(self):
        return self.__str__()
    
class Path:
    data = []
    match = -1
    active = False
    
""" Class defining a convolution """
class Convolution:
    _k=0
    _r=0
    _states = []
    _buffer = []
    _mapping = []
    _outputStates = []
    _stateTransitionTable = []
    _STTI_StartState = 0
    _STTI_EndState = 3
    _STTI_Result = 1
    _STTI_EndStateNumber = 5
    _paths = []
    _tmpPaths = []
    
    def _createStates(self):
        self._states= []
        i=0        
        ba = BinaryArray(self._k-1)
        
        nofStates = 2**(self._k-1)
        while (i<nofStates):
            self._states.append( State(ba.clone()) )
            ba.add(1)
            i+=1
        return
    
    def _clearBuffer(self):    
        self._buffer = []
        i = 0
        while i<self._k-1:
            self._buffer.append(0)
            i+=1 
            
    def _clearPaths(self):
        self._paths = []
        self._tmpPaths = []
        i=0
        while (i< 2 ** (self._k-1)):
            self._paths.append(Path())
            self._tmpPaths.append(Path())
            i+=1 
            
    def _createOutputStates(self):
        nofStates = 2 ** len(self._mapping)
        i = 0
        ba = BinaryArray(len(self._mapping))
        while (i<nofStates):
            self._outputStates.append(OutputState(ba.clone()))
            ba.add(1)
            i+=1
 
    def _createStateTransitionTable(self):
        ba = BinaryArray(self._k-1)
        
        i = 0
        self._stateTransitionTable = []
        while (i < 2**(self._k-1)):
            self._buffer = ba._value[:]   # copy state to buffer
            zero = self.insert(0)
            bufferZero = self._buffer
            self._buffer = ba._value[:]   # copy state to buffer
            one = self.insert(1)
            bufferOne = self._buffer
            
            index = -1
            i2 = 0
            endStateNumberZero = -1
            endStateNumberOne = -1
            while (i2 < len(self._states)):
                a = self._states[i2]._state._value
                if (str(a)==str(bufferZero) ):
                    endStateNumberZero = i2
                    break
                i2+=1
            i2 = 0
            while (i2 < len(self._states)):
                a = self._states[i2]._state._value
                if (str(a)==str(bufferOne)):
                    endStateNumberOne = i2
                    break
                i2+=1
                
            #endStateNumberZero = self._states.index(bufferZero._value)
            #endStateNumberOne = self._states.index(bufferOne._value)
            
            """     start state ,  result: 0 ,   1,   output state:  0,         1, endStateNumber: 0,   1 """
            data = (ba._value[:],        zero, one,         bufferZero, bufferOne,   endStateNumberZero, endStateNumberOne)
            
            self._stateTransitionTable.append(data)
            ba.add(1)
            i+=1
            
        self._clearBuffer()
 
    def insert(self,bit):
        if bit <> 0:
            bit = 1
        
        i = 0
        out = []

        mappingLength = len(self._mapping)
        self._buffer.insert(0, bit)
        while (i<mappingLength):
            v = 0        
            for a in self._mapping[i]:
#                if (a==0):
#                    v = v ^ bit
#                else:
#                    v = v ^ self._buffer[a-1]
                v = v ^ self._buffer[a]
            out.append(v)
            i+=1
        
        self._buffer.pop()
#        self._buffer.insert(0, bit)
            
        return out
    
    def insertSeq(self,sequence):
        result = []
        for a in sequence:
            result.append(self.insert(a))
        return result
    
    def _match(self,bits1,bits2):
        
        i = 0
        matchCount = 0
        while ( i < len(bits1)):
            if (bits1[i] == bits2[i]):
                matchCount+=1                
            i+=1
        return matchCount
    
    def _decodeStep(self,stateNumber, seqPartInput, guessBit):
        
        endState = self._stateTransitionTable[stateNumber][self._STTI_EndState+guessBit]
        endStateNumber = self._stateTransitionTable[stateNumber][self._STTI_EndStateNumber+guessBit]
        seq = self._stateTransitionTable[stateNumber][self._STTI_Result+guessBit]
        match = self._match(seqPartInput, seq)
        
        return (match, endState, endStateNumber)
        
    def _decodePath(self, pathIndex, step, sequence, OneZeroArray):
        if (self._paths[pathIndex].active == False):
            return
        
        zero = self._decodeStep(pathIndex, sequence[step], 0)
        one  = self._decodeStep(pathIndex, sequence[step], 1)
        
        zeroMatch = self._paths[pathIndex].match + zero[0]
        oneMatch  = self._paths[pathIndex].match + one[0]
        
        zeroEndStateNumber = zero[2]
        oneEndStateNumber  = one[2]
        
        allowOne = allowZero = False
        if (OneZeroArray[0] == 0):
            allowZero = True
        if (OneZeroArray[1] == 0):
            allowZero = True
        if (OneZeroArray[0] == 1):
            allowOne = True
        if (OneZeroArray[1] == 1):
            allowOne = True
        
        if (allowZero == True) & (self._tmpPaths[zeroEndStateNumber].match <= zeroMatch):
            self._tmpPaths[zeroEndStateNumber].match = zeroMatch
            self._tmpPaths[zeroEndStateNumber].data = self._paths[pathIndex].data[:]
            self._tmpPaths[zeroEndStateNumber].data.append(0)
            self._tmpPaths[zeroEndStateNumber].active = True
            
        if (allowOne == True) & (self._tmpPaths[oneEndStateNumber].match <= oneMatch):
            self._tmpPaths[oneEndStateNumber].match = oneMatch
            self._tmpPaths[oneEndStateNumber].data  = self._paths[pathIndex].data[:]
            self._tmpPaths[oneEndStateNumber].data.append(1)
            self._tmpPaths[oneEndStateNumber].active = True
            
    def _advancePaths(self):
        self._paths = self._tmpPaths
        self._tmpPaths = []
        i = 0
#        print "----------------"
        while (i < 2 ** (self._k-1)):
            self._tmpPaths.append(Path())
#            print "Path " + str(i) + ": " + str(self._paths[i].data)
            i+=1
            

    def _getHighestPath(self):
        maxMatch = -1
        matchIndex = -1
        i = 0 
        while ( i < 2 ** (self._k-1)):
            if (self._paths[i].match <= maxMatch):
                maxMatch = self._paths[i].match
                matchIndex = i
            i+=1
        matchIndex = 0
        return self._paths[matchIndex]
        
        
    def decodeSeq(self,sequence, allowOnlyZeroesAfterLen):
        self._clearPaths()
        
        if (len(sequence) == 0):
            raise Exception("Invalid length of sequence")
            
        """ assume starting state is zero """ 
        self._paths[0].active = True       
        self._decodePath(0, 0, sequence,[0,1])
        self._advancePaths()
        
        i = 1
        while (i < len(sequence)):
            pIndex = 0
            while (pIndex < 2 ** (self._k-1) ):
                oneZeroArray = [0,1]
                
                if (i >= allowOnlyZeroesAfterLen):
                    oneZeroArray = [0,0]
                    
                self._decodePath(pIndex, i, sequence, oneZeroArray)
                pIndex+=1
            self._advancePaths()
            i+=1
        
        path = self._getHighestPath()
        
        return path.data
        
 
    def __init__(self,k,r,mapping):
        if ((k > 0) & (r > 0)):
            self._k = k
            self._r = r            
            print "Creating....."

            self._createStates()
            self._clearBuffer()
            self._mapping = mapping
            self._mappingState = 0
            self._createOutputStates()
            self._createStateTransitionTable()
            self._clearPaths()
            
            print "Done!"
        else:
            print "Error wrong parameters for k and/or m when creating object of " + self.__class__.__name__
           
            
        
        

def main():
    import random
    conv = Convolution(9,2,[[0,2,3,4,8],[0,1,2,3,5,7,8]])
    # 101110001  111101011
    print conv._states
    print conv._buffer
    
    print "Output states: " + str(conv._outputStates)
    repSeq = [1,0,0]
    startSeq = []
    
    i=0
    while(i<100):
        startSeq.append(random.randint(0, 1))
        startSeq.append(random.randint(0, 1))
        startSeq.append(random.randint(0, 1))
        #startSeq.extend(repSeq)
        i+=1
        
    print "Start sequence: " + str(startSeq)
    startSeq.extend([0,0,0,0,0,0,0,0])
    coded = conv.insertSeq(startSeq)

    i = 0
    i2 = 0
    cycle = 10
    while (i<len(coded)):
        if (i%cycle == 0):
            # add noise
            if (coded[i][i2%2] == 0):
                coded[i][i2%2] = 1
            else:
                coded[i][i2%2] = 0
             
        i+=1
        i2+=1
    
    print "Coded sequence: " + str(coded)
    
    decoded = conv.decodeSeq(coded,99999999)
    decoded.pop()
    decoded.pop()
    decoded.pop()
    decoded.pop()
    decoded.pop()
    decoded.pop()
    decoded.pop()
    decoded.pop()
    
    print "Decoded sequence: " + str(decoded)
    
    i=0
    ok = True
    while(i<len(decoded)):
        if (decoded[i] != startSeq[i]):
            ok = False
            print "error at index: " + str(i)
        i+=1
    if (ok==False):
        print "Decoding NOT ok, Errors detected"
    else:
        print "Decoded OK!!!"
            
    return


if __name__ == '__main__':
    main()
